"""
670. 最大交换 - 算法测试框架

用于测试三种贪心算法的正确性和性能
"""

import time
import sys
from typing import List, Tuple
from alg import Solution, analyze_number, print_analysis
from gen import TestDataGenerator, analyze_number_properties

class AlgorithmTester:
    """算法测试器"""
    
    def __init__(self):
        self.solution = Solution()
        self.generator = TestDataGenerator()
    
    def brute_force_solution(self, num: int) -> int:
        """暴力解法用于验证正确性"""
        digits = list(str(num))
        n = len(digits)
        max_result = num
        
        # 尝试所有可能的交换
        for i in range(n):
            for j in range(i + 1, n):
                # 交换位置i和j
                digits[i], digits[j] = digits[j], digits[i]
                
                # 计算交换后的数字
                swapped_num = int(''.join(digits))
                max_result = max(max_result, swapped_num)
                
                # 恢复原状
                digits[i], digits[j] = digits[j], digits[i]
        
        return max_result
    
    def test_correctness(self) -> bool:
        """测试算法正确性"""
        print("=" * 60)
        print("算法正确性测试")
        print("=" * 60)
        
        all_passed = True
        test_cases = self.generator.generate_all_test_cases()
        
        for i, (name, num) in enumerate(test_cases[:20], 1):  # 只测试前20个用例
            print(f"\n测试用例 {i}: {name}")
            print(f"输入数字: {num}")
            
            try:
                # 三种贪心方法
                start_time = time.time()
                result1 = self.solution.maximumSwap(num)
                time1 = time.time() - start_time
                
                start_time = time.time()
                result2 = self.solution.maximumSwap_simple(num)
                time2 = time.time() - start_time
                
                start_time = time.time()
                result3 = self.solution.maximumSwap_bucket(num)
                time3 = time.time() - start_time
                
                # 暴力验证方法（只对小数字使用）
                if len(str(num)) <= 6:
                    start_time = time.time()
                    brute_result = self.brute_force_solution(num)
                    brute_time = time.time() - start_time
                    
                    print(f"优化贪心法: {result1} ({time1:.6f}s)")
                    print(f"简单贪心法: {result2} ({time2:.6f}s)")
                    print(f"桶排序法: {result3} ({time3:.6f}s)")
                    print(f"暴力验证法: {brute_result} ({brute_time:.6f}s)")
                    
                    # 检查一致性
                    all_same = result1 == result2 == result3 == brute_result
                    print(f"所有结果一致: {'✓' if all_same else '✗'}")
                    
                    if not all_same:
                        print("❌ 测试失败！")
                        all_passed = False
                        
                else:
                    print(f"优化贪心法: {result1} ({time1:.6f}s)")
                    print(f"简单贪心法: {result2} ({time2:.6f}s)")
                    print(f"桶排序法: {result3} ({time3:.6f}s)")
                    
                    # 只检查三种贪心算法的一致性
                    greedy_same = result1 == result2 == result3
                    print(f"贪心算法结果一致: {'✓' if greedy_same else '✗'}")
                    
                    if not greedy_same:
                        print("❌ 贪心算法结果不一致！")
                        all_passed = False
                    
            except Exception as e:
                print(f"❌ 测试出错: {e}")
                all_passed = False
        
        print(f"\n{'✅ 所有测试通过！' if all_passed else '❌ 部分测试失败'}")
        return all_passed
    
    def test_performance(self):
        """性能测试"""
        print("\n" + "=" * 60)
        print("算法性能测试")
        print("=" * 60)
        
        # 性能测试用例
        performance_cases = [
            ("2位数", 87),
            ("4位数", 2736),
            ("6位数", 876543),
            ("8位数", 98765432),
            ("递增序列", 12345678),
            ("递减序列", 87654321),
            ("重复数字", 77889900),
        ]
        
        print(f"{'测试用例':<12} {'数字':<10} {'位数':<4} {'优化贪心(s)':<12} {'简单贪心(s)':<12} {'桶排序(s)':<12} {'结果':<10}")
        print("-" * 85)
        
        for name, num in performance_cases:
            # 测试三种算法
            start_time = time.time()
            result1 = self.solution.maximumSwap(num)
            time1 = time.time() - start_time
            
            start_time = time.time()
            result2 = self.solution.maximumSwap_simple(num)
            time2 = time.time() - start_time
            
            start_time = time.time()
            result3 = self.solution.maximumSwap_bucket(num)
            time3 = time.time() - start_time
            
            # 检查结果一致性
            consistent = result1 == result2 == result3
            
            print(f"{name:<12} {num:<10} {len(str(num)):<4} {time1:<12.8f} {time2:<12.8f} {time3:<12.8f} {result1 if consistent else 'ERROR':<10}")
    
    def test_special_cases(self):
        """测试特殊用例"""
        print("\n" + "=" * 60)
        print("特殊用例测试")
        print("=" * 60)
        
        special_cases = [
            ("单个数字", 5),
            ("两位相同", 77),
            ("已经最大", 9876),
            ("全相同", 8888),
            ("包含0", 1032),
            ("末尾是0", 1230),
            ("开头是最大", 9123),
            ("最大在末尾", 1239),
            ("重复最大值", 9919),
            ("对称数", 12321),
        ]
        
        for name, num in special_cases:
            print(f"\n{name}: {num}")
            
            # 分析数字性质
            analysis = analyze_number_properties(num)
            print(f"数字序列: {' '.join(analysis['digits'])}")
            print(f"严格递减: {analysis['is_strictly_descending']}")
            print(f"有重复: {analysis['has_duplicates']}")
            
            # 测试算法
            result1 = self.solution.maximumSwap(num)
            result2 = self.solution.maximumSwap_simple(num)
            result3 = self.solution.maximumSwap_bucket(num)
            
            print(f"算法结果: {result1}")
            print(f"结果一致: {'✓' if result1 == result2 == result3 else '✗'}")
            
            # 分析交换策略
            if result1 > num:
                print(f"交换有效，从 {num} 增加到 {result1}")
            else:
                print("无需交换或无法改善")
    
    def analyze_swap_strategy(self, num: int):
        """分析交换策略"""
        print(f"\n=== 交换策略分析: {num} ===")
        
        digits = list(str(num))
        n = len(digits)
        
        # 显示原数字
        print(f"原数字: {''.join(digits)}")
        print(f"位置:   {' '.join(str(i) for i in range(n))}")
        
        # 找到贪心算法的交换位置
        result = self.solution.maximumSwap(num)
        
        if result == num:
            print("无需交换，已经是最优")
            return
        
        # 通过比较找出交换了哪两个位置
        result_digits = list(str(result))
        swap_positions = []
        
        for i in range(n):
            if digits[i] != result_digits[i]:
                swap_positions.append(i)
        
        if len(swap_positions) == 2:
            pos1, pos2 = swap_positions
            print(f"交换位置: {pos1} ↔ {pos2}")
            print(f"交换数字: {digits[pos1]} ↔ {digits[pos2]}")
            print(f"结果: {result}")
            print(f"增加: {result - num}")
        else:
            print("交换分析失败")
    
    def test_algorithm_variants(self):
        """测试算法变体"""
        print("\n" + "=" * 60)
        print("算法变体对比")
        print("=" * 60)
        
        test_numbers = [2736, 9973, 1234, 98368, 1993]
        
        for num in test_numbers:
            print(f"\n测试数字: {num}")
            
            # 三种算法的执行时间对比
            algorithms = [
                ("优化贪心", self.solution.maximumSwap),
                ("简单贪心", self.solution.maximumSwap_simple),
                ("桶排序", self.solution.maximumSwap_bucket),
            ]
            
            results = {}
            
            for name, algo in algorithms:
                start_time = time.time()
                result = algo(num)
                execution_time = time.time() - start_time
                results[name] = (result, execution_time)
                print(f"{name}: {result} ({execution_time:.8f}s)")
            
            # 检查结果一致性
            values = [result for result, _ in results.values()]
            if len(set(values)) == 1:
                print("✓ 所有算法结果一致")
            else:
                print("✗ 算法结果不一致")
            
            # 分析交换策略
            self.analyze_swap_strategy(num)
    
    def run_all_tests(self):
        """运行所有测试"""
        print("670. 最大交换 - 完整测试套件")
        print("=" * 60)
        
        try:
            # 1. 正确性测试
            if not self.test_correctness():
                print("❌ 正确性测试失败，停止后续测试")
                return False
            
            # 2. 特殊用例测试
            self.test_special_cases()
            
            # 3. 算法变体对比
            self.test_algorithm_variants()
            
            # 4. 性能测试
            self.test_performance()
            
            print("\n" + "=" * 60)
            print("✅ 所有测试完成！")
            print("=" * 60)
            
            return True
            
        except Exception as e:
            print(f"❌ 测试过程中出错: {e}")
            return False

def main():
    """主测试函数"""
    tester = AlgorithmTester()
    
    print("选择测试模式:")
    print("1. 完整测试")
    print("2. 只测试正确性")
    print("3. 只测试性能")
    print("4. 只测试特殊用例")
    print("5. 算法变体对比")
    
    try:
        choice = input("请选择 (1-5): ").strip()
        
        if choice == "1":
            tester.run_all_tests()
        elif choice == "2":
            tester.test_correctness()
        elif choice == "3":
            tester.test_performance()
        elif choice == "4":
            tester.test_special_cases()
        elif choice == "5":
            tester.test_algorithm_variants()
        else:
            print("运行完整测试...")
            tester.run_all_tests()
            
    except KeyboardInterrupt:
        print("\n测试被用户中断")
    except Exception as e:
        print(f"测试出错: {e}")

if __name__ == "__main__":
    main()
